home *** CD-ROM | disk | FTP | other *** search
/ Tech Arsenal 1 / Tech Arsenal (Arsenal Computer).ISO / tek-02 / sortdemo.zip / SDSORT03.INC < prev    next >
Text File  |  1992-04-15  |  3KB  |  72 lines
  1. (*
  2. ╔═══════════════════════════════════════════════════════════════════════════╗
  3. ║ Turbo Pascal 6.0 Include File : SDSORT03.INC                              ║
  4. ╟───────────────────────────────────────────────────────────────────────────╢
  5. ║ Program : SORTDEMO.PAS                                                    ║
  6. ╟───────────────────────────────────────────────────────────────────────────╢
  7. ║ Version : 1.0                                                             ║
  8. ╟───────────────────────────────────────────────────────────────────────────╢
  9. ║ Copyright (c) 1992  by  Jon S. Russell                                    ║
  10. ╟───────────────────────────────────────────────────────────────────────────╢
  11. ║ Selection sort routine for SORTDEMO.PAS                                   ║
  12. ╚═══════════════════════════════════════════════════════════════════════════╝
  13.                                                                            *)
  14. procedure SelectionSort (var Info : InfoType);
  15. var
  16.   Current  : IndexType;
  17.   Smallest : IndexType;
  18.  
  19.   (*───────────────────────────────────────────────────────────────────────*)
  20.  
  21.   function MinIndex (var List       : ListType;
  22.                          StartIndex : IndexType;
  23.                          EndIndex   : IndexType) : IndexType;
  24.  
  25.   var
  26.     Min   : IndexType;  (* index of smallest element so far *)
  27.     Index : IndexType;  (* loop control variable            *)
  28.  
  29.     (* MinIndex = index of smallest element in the subarray *)
  30.     (* List[StartIndex] .. List[EndIndex].                  *)
  31.  
  32.   begin (* MinIndex *)
  33.     Min := StartIndex;
  34.  
  35.     (* Loop Invariant: List[Min] is the smallest element *)
  36.     (* in List[StartIndex] .. List[Index-1] AND          *)
  37.     (* StartIndex <= Index <= EndIndex+1.                *)
  38.  
  39.     for Index := StartIndex+1 to EndIndex do
  40.       if (List[Index].Key < List[Min].Key) then Min := Index;
  41.  
  42.     MinIndex := Min;
  43.   end;  (* MinIndex *)
  44.  
  45.   (*───────────────────────────────────────────────────────────────────────*)
  46.  
  47. begin  (* SelectionSort *)
  48.   Current := 1;  (* index of first unsorted element *)
  49.  
  50.   (* Loop Invariant: 1 <= Current <= Info.Len AND the  *)
  51.   (* values in List[1] .. List[Current-1] are sorted   *)
  52.   (* and are less than or equal to the unsorted values *)
  53.   (* in List[Current] .. Info[Len].                    *)
  54.  
  55.   while Current < Info.Len do
  56.     begin
  57.       (* Find the smallest element in the unsorted part. *)
  58.       Smallest := MinIndex(Info.List, Current, Info.Len);
  59.  
  60.       (* Swap the Current element and the smallest  *)
  61.       (* element in the unsorted part of the array. *)
  62.       Swap(Info, Current, Smallest);
  63.  
  64.       (* Shrink the unsorted part of the array. *)
  65.       Inc(Current);
  66.     end; (* while *)
  67.  
  68.   Info.Sorted := true;  (* set flag *)
  69. end;   (* SelectionSort *)
  70.  
  71. (*─────────────────────────────────────────────────────────────────────────*)
  72.